package LeetCode;
// todo 1
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

public class LC502_2 {
    // 贪心+优先队列
    private int ans = 0;

    public static void main(String[] args) {
        LC502_2 lc502 = new LC502_2();
        System.out.println(lc502.findMaximizedCapital(1, 2, new int[]{1, 2, 3}, new int[]{1, 1, 2}));
    }

    public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {
        int len = profits.length;
        int[][] values = new int[len][2];
        for (int i = 0; i < len; i++) {
            values[i][0] = capital[i];
            values[i][1] = profits[i];
        }
        Arrays.sort(values,(a,b)->a[0]-b[0]);
        PriorityQueue<Integer> queue = new PriorityQueue<>(k, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2-o1;
            }
        }); // 将限定条件下的value放进来
        int index =0;
        for (int i = 0; i < k; i++) {
            while (index<len && w>=values[index][0]){
                queue.add(values[index++][1]);
            }
            if(!queue.isEmpty()) w += queue.poll();
        }
        return w;

    }


}
